package com.leetcode.algorithm.y19.m01;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import com.leetcode.algorithm.common.TreeNode;

/**
 * leetcode-cn.com
 * (done)617. 合并二叉树
 * (done)637. 二叉树的层平均值
 * (done)235. 二叉搜索树的最近公共祖先
 * (done)236. 二叉树的最近公共祖先
 * (done)965. 单值二叉树
 * (done)704. 二分查找
 * 
 * @author: jie.deng
 * @time: 2019年1月18日 下午5:48:36
 */
public class MySolution0119 {
	
	/**
	 * 617. 合并二叉树
	 * 
     * 给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
     * 
     * 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
     * 
     * 示例 1:
     * 
     * 输入: 
     * 	Tree 1                     Tree 2                  
     *           1                         2                             
     *          / \                       / \                            
     *         3   2                     1   3                        
     *        /                           \   \                      
     *       5                             4   7                  
     * 输出: 
     * 合并后的树:
     * 	     3
     * 	    / \
     * 	   4   5
     * 	  / \   \ 
     * 	 5   4   7
     * 注意: 合并必须从两个树的根节点开始。
	 * @param t1
	 * @param t2
	 * @return
	 */
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
		if (t1 == null) {
			return t2;
		}
		if (t2 == null) {
			return t1;
		}
		TreeNode tn = new TreeNode(t1.val + t2.val);
		tn.left = mergeTrees(t1.left, t2.left);
		tn.right = mergeTrees(t1.right, t2.right);
		return tn;
    }
    
    /**
     * 637. 二叉树的层平均值
     * 
     * 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.
     * 
     * 示例 1:
     * 
     * 输入:
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * 输出: [3, 14.5, 11]
     * 解释:
     * 第0层的平均值是 3,  第1层是 14.5, 第2层是 11. 因此返回 [3, 14.5, 11].
     * 注意：
     * 
     * 节点值的范围在32位有符号整数范围内。
     * @param root
     * @return
     */
	public List<Double> averageOfLevels(TreeNode root) {
		List<List<Integer>> rootList = new ArrayList<List<Integer>>();
		averageOfLevels(root, 0, rootList);

		List<Double> retList = new ArrayList<Double>();
		if (rootList != null) {
			for (List<Integer> levelList : rootList) {
				if (levelList != null) {
					double sum = 0;
					for (Integer val : levelList) {
						sum += val;
					}
					retList.add(sum / levelList.size());
				}
			}
		}
		return retList;
	}

	private void averageOfLevels(TreeNode t, int level, List<List<Integer>> rootList) {
		if (t == null) {
			return;
		}
		List<Integer> levelList = null;
		if (rootList.size() > level) {
			levelList = rootList.get(level);
		} else {
			levelList = new ArrayList<Integer>();
			rootList.add(levelList);
		}
		levelList.add(t.val);
		averageOfLevels(t.left, level + 1, rootList);
		averageOfLevels(t.right, level + 1, rootList);
	}
	
    /**
     * 235. 二叉搜索树的最近公共祖先
     * 
     * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
     * 
     * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
     * 
     * 例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]
     * 示例 1:
     * 
     * 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
     * 输出: 6 
     * 解释: 节点 2 和节点 8 的最近公共祖先是 6。
     * 示例 2:
     * 
     * 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
     * 输出: 2
     * 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
     *  
     * 
     * 说明:
     * 
     * 所有节点的值都是唯一的。
     * p、q 为不同节点且均存在于给定的二叉搜索树中。
     * @param root
     * @param p
     * @param q
     * @return
     */
	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		if (root == null) {
			return null;
		}
		int valP = p.val;
		int valQ = q.val;
		return lowestCommonAncestor(root, valP, valQ);
	}

	private TreeNode lowestCommonAncestor(TreeNode node, int valP, int valQ) {
		if (node == null) {
			return null;
		}
		if ((node.val >= valP && node.val <= valQ) || (node.val <= valP && node.val >= valQ)) {
			return node;
		}
		TreeNode left = node.left;
		TreeNode lowestNode = lowestCommonAncestor(left, valP, valQ);
		return lowestNode == null ? lowestCommonAncestor(node.right, valP, valQ) : lowestNode;
	}
	
    /**
     * 236. 二叉树的最近公共祖先
     * 
     * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
     * 
     * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
     * 
     * 例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]
     * 示例 1:
     * 
     * 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
     * 输出: 3
     * 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
     * 示例 2:
     * 
     * 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
     * 输出: 5
     * 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
     *  
     * 
     * 说明:
     * 
     * 所有节点的值都是唯一的。
     * p、q 为不同节点且均存在于给定的二叉树中。
     * @param root
     * @param p
     * @param q
     * @return
     */
	public TreeNode lowestCommonAncestorMedium(TreeNode root, TreeNode p, TreeNode q) {
		if (root == null) {
			return null;
		}
		Stack<TreeNode> pStack = new Stack<TreeNode>();
		Stack<TreeNode> qStack = new Stack<TreeNode>();
		findAncestorNode(root, p, pStack);
		findAncestorNode(root, q, qStack);
		while (!pStack.empty()) {
			TreeNode ancestorNode = pStack.pop();
			if (qStack.contains(ancestorNode)) {
				return ancestorNode;
			}
		}
		return null;
	}

	private boolean findAncestorNode(TreeNode node, TreeNode p, Stack<TreeNode> stack) {
		stack.push(node);
		if (node.val == p.val) {
			return true;
		}
		if (node.left != null) {
			boolean flag = findAncestorNode(node.left, p, stack);
			if (flag) {
				return flag;
			}
		}
		if (node.right != null) {
			boolean flag = findAncestorNode(node.right, p, stack);
			if (flag) {
				return flag;
			}
		}
		stack.pop();
		return false;
	}

	/**
     * 965. 单值二叉树
     * 
     * 如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
     * 
     * 只有给定的树是单值二叉树时，才返回 true；否则返回 false。
     * 
     * 示例 1：
     * 输入：[1,1,1,1,1,null,1]
     * 输出：true
     * 
     * 示例 2：
     * 输入：[2,2,2,5,2]
     * 输出：false
     * 
     * 提示：
     * 
     * 给定树的节点数范围是 [1, 100]。
     * 每个节点的值都是整数，范围为 [0, 99] 。
     * @param root
     * @return
     */
	public boolean isUnivalTree(TreeNode root) {
		if (root == null) {
			return true;
		}
		return isUnivalTree(root.left, root.val) && isUnivalTree(root.right, root.val);
	}

	private boolean isUnivalTree(TreeNode node, int val) {
		if (node == null) {
			return true;
		}
		return node.val == val && isUnivalTree(node.left, val) && isUnivalTree(node.right, val);
	}
	
	/**
	 * 704. 二分查找
	 * 
     * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
     * 
     * 
     * 示例 1:
     * 
     * 输入: nums = [-1,0,3,5,9,12], target = 9
     * 输出: 4
     * 解释: 9 出现在 nums 中并且下标为 4
     * 示例 2:
     * 
     * 输入: nums = [-1,0,3,5,9,12], target = 2
     * 输出: -1
     * 解释: 2 不存在 nums 中因此返回 -1
     *  
     * 
     * 提示：
     * 
     * 你可以假设 nums 中的所有元素是不重复的。
     * n 将在 [1, 10000]之间。
     * nums 的每个元素都将在 [-9999, 9999]之间。
	 * @param nums
	 * @param target
	 * @return
	 */
	public int search(int[] nums, int target) {
		int l = 0;
		int r = nums.length - 1;
		int m = (l + r) / 2;
		while (r >= l && nums[m] != target) {
			if (nums[m] > target) {
				r = m - 1;
			} else {
				l = m + 1;
			}
			m = (l + r) / 2;
		}
		if (nums[m] == target) {
			return m;
		}
		return -1;
	}
    
}
